Weak NP-completeness
SET OF COMPUTATIONAL PROBLEMS FOR WHICH THERE IS AN ALGORITHM SOLVING THEM IN POLYNOMIAL TIME IN THE DIMENSION OF THE PROBLEM AND THE MAGNITUDES OF THE DATA INVOLVED (IF GIVEN AS INTEGERS), RATHER THAN THE BASE-TWO LOGARITHMS OF THEIR MAGNITUDES
Weakly NP-complete; Weakly NP-hard
In computational complexity, an NP-complete (or NP-hard) problem is weakly NP-complete (or weakly NP-hard) if there is an algorithm for the problem whose running time is polynomial in the dimension of the problem and the magnitudes of the data involved (provided these are given as integers), rather than the base-two logarithms of their magnitudes. Such algorithms are technically exponential functions of their input size and are therefore not considered polynomial.